移除链表元素

题目描述：删除链表中等于给定值 val 的所有节点。

示例：

输入: 1->2->6->3->4->5->6, val = 6
输出: 1->2->3->4->5

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
  public ListNode removeElements(ListNode head, int val) {

  }
}

方法一：单指针

此题和前面 ”删除链表的节点“ 相似，但是此题多了个条件：需要删除全部指定的节点。

解题思路可以和之前的一致，即遇到值为 val 的直接删除。需要注意的是头结点的处理，这里是最后再处理。

class Solution {
  public ListNode removeElements(ListNode head, int val) {
    if(head == null) return null;

    ListNode temp = head; // 用来遍历的节点
    while(temp.next != null) { // 因为我们是对下一个节点执行判断和删除操作，所以下一个节点不能为null
      if(temp.next.val == val) { // 如果下一个节点值等于val
        temp.next = temp.next.next; //修改指针，执行删除操作
      } else {
        temp = temp.next; // 否则，正常遍历
      }
    }
    return head.val == val ? head.next : head; // 因为while循环没有判断头结点，所以这里还需要判断一下
  }
}

复杂度分析：

• 时间复杂度：O(N) ，N 为链表的长度，最坏情况下，要删除的结点位于链表末尾，这时我们需要遍历整个链表
• 空间复杂度：O(1)

执行结果：通过

• 执行用时：1 ms, 在所有 Java 提交中击败了99.72%的用户
• 内存消耗：40.4 MB, 在所有 Java 提交中击败了97.51%的用户

方法二：哨兵节点 + 双指针

该题的核心是什么时候处理头结点？这里是使用一个辅助头结点，统一处理链表，就不需要额外考虑原头结点的问题了。

1. 先创建哨兵节点，将哨兵节点的 next 指向链表头节点
2. 定义双指针分别指向哨兵节点和链表头节点，移动双指针依次判断链表节点是否为要移除的节点

class Solution {
  public ListNode removeElements(ListNode head, int val) {
    ListNode node = new ListNode(0);
    node.next = head;
    ListNode pre = node, cur = head;
    while(cur != null) {
      if(cur.val == val) {
        pre.next = cur.next;
      } else {
        pre = cur;
      }
      cur = cur.next;
    }
    return node.next;
  }
}

复杂度分析：

• 时间复杂度：O(N) ，N 为链表的长度，最坏情况下，要删除的结点位于链表末尾，这时我们需要遍历整个链表
• 空间复杂度：O(1)

执行结果：通过

• 执行用时：1 ms, 在所有 Java 提交中击败了99.72%的用户
• 内存消耗：41.1 MB, 在所有 Java 提交中击败了8.79%的用户

方法三：递归

class Solution {
  public ListNode removeElements(ListNode head, int val) {
    if(head == null)
      return null;
    head.next = removeElements(head.next,val);
    if(head.val == val){
      return head.next;
    }else{
      return head;
    }
  }
}

执行结果：通过

• 执行用时：1 ms, 在所有 Java 提交中击败了99.72%的用户

• 内存消耗：41.2 MB, 在所有 Java 提交中击败了5.51%的用户

复杂度分析：

• 时间复杂度：O(N) ，递归次数为链表长度
• 空间复杂度：迭代使用栈内存，所以为 O(N)